백준 5427 불

2018-01-31

Algorithm

백준 5427 불은 전형적인 BFS 문제이다. 처음 시작 위치가 주어지고 불이 번질 때 지정된 위치로 탈출 할 수 있는가를 판단하는 문제이다.

사람의 위치를 퍼지게 하기 위한 queue와 불이 퍼지게 하기 위한 위치를 담긴 queue인 2개의 queue를 이용하여 시뮬레이션 하였다. 사실 생각해보니까 queue를 따로 두지 않고 사람, 불에 대한 타입을 정의한 뒤 이를 queue에 넣어주면 하나의 queue로도 구현이 가능할 것 같다.

아무튼 이러한 방식을 통해 사람의 위치와 불의 위치는 1초의 시간이 지날때 마다 인접으로 퍼져나가게 된다. 현재 위치에서 상,하,좌,우의 위치값으로 이동이 가능하면 이동을 하고 왔던 길에 대해서 다시 오지 않도록 visited 배열을 이용해 표시해둔다. -> 넣은 좌표 위치 값에 대하여 큐에 또 다시 중복으로 들어가게 된다면 큐가 터져서 메모리 초과가 날 것이다.

백준 5427은 특정 위치에 대해 인접한 부분으로 움직이기 위하여 bfs를 이용하여 푸는 문제였다.

#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<stdlib.h>
#include<string>
#include<set>
#define INF 987654321
#define ll long long
using namespace std;

int n, m, k;

char map[1001][1001];

int visited2[1001][1001];


int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

bool inArea(int x, int y)
{
	if (0 <= x&&x < m && 0 <= y&&y < n)
		return true;
	return false;
}


void printMap()
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << map[i][j];
		}
		cout << endl;
	}
}


int main()
{
	//freopen("input.txt", "r", stdin);
	int testCase;
	scanf("%d", &testCase);

	for (int t = 0; t < testCase; t++)
	{
		scanf("%d %d", &n, &m);
		memset(visited2, 0, sizeof(visited2));

		int startx = 0;
		int starty = 0;

		vector<pair<int, int>> fire;

		bool find = false;

		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				cin >> map[i][j];

				if (map[i][j] == '@')
				{
					startx = i;
					starty = j;
				}
				if (map[i][j] == '*')
				{
					fire.push_back(make_pair(i, j));
				}
			}
		}

		queue<pair<int, int>> queue1;
		queue<pair<int, int>> queue2;

		for (int i = 0; i < fire.size(); i++)
		{
			queue1.push(make_pair(fire[i].first, fire[i].second));
		}

		queue2.push(make_pair(startx, starty));
		visited2[startx][starty] = 1;

		int cnt = 0;


		while (!queue2.empty())
		{
			cnt++;
			int q2size = queue2.size();
			for (int i = 0; i < q2size; i++)
			{
				int cx = queue2.front().first;
				int cy = queue2.front().second;

				queue2.pop();

				if (map[cx][cy] == '*')
					continue;

				for (int j = 0; j < 4; j++)
				{
					int nextx = cx + dx[j];
					int nexty = cy + dy[j];

					if (inArea(nextx, nexty))
					{
						if (!visited2[nextx][nexty] && map[nextx][nexty] =='.')
						{
							visited2[nextx][nexty] = 1;
							queue2.push(make_pair(nextx, nexty));
						}
					}
					else
					{
						printf("%d\n", cnt);
						find = true;
						break;
					}
				}
				if (find)
					break;
			}

			if (find)
				break;


			int q1size = queue1.size();

			for (int i = 0; i < q1size; i++)
			{
				int cx = queue1.front().first;
				int cy = queue1.front().second;
				queue1.pop();

				for (int j = 0; j < 4; j++)
				{
					int nextx = cx + dx[j];
					int nexty = cy + dy[j];

					if (inArea(nextx, nexty) && map[nextx][nexty] == '.')
					{
						queue1.push(make_pair(nextx, nexty));
						map[nextx][nexty] = '*';
					}
				}
			}


		}

		if (!find)
			printf("IMPOSSIBLE\n");
	}


}

Gunner

ProgrammingAlgorithm

백준 5427 불